package datastructure.sort;

import java.util.Comparator;

/**
 * Description：
 * Author: zhangc
 * Date：2017/6/28 20:16
 */
public class MergeSort {

    public static <T extends Comparable<? super T>> void sort(T[] array) {
        mergeSort(array, 0, array.length - 1);
    }


    private static <T extends Comparable<? super T>> void mergeSort(T[] array, int low, int high) {

        int mid = (low + high) >> 1;
        if (low < high) {
            // 左边
            mergeSort(array, low, mid);
            // 右边
            mergeSort(array, mid + 1, high);
            // 左右归并
            merge(array, low, mid, high);
        }
    }

    private static <T extends Comparable<? super T>> void merge(T[] array, int low, int mid, int high) {
        Object[] temp = new Object[ high - low + 1 ];
        int i = low;// 左指针
        int j = mid + 1;// 右指针
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (array[ i ].compareTo(array[ j ]) < 0)
                temp[ k++ ] = array[ i++ ];
            else {
                temp[ k++ ] = array[ j++ ];
            }
        }

        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[ k++ ] = array[ i++ ];
        }

        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[ k++ ] = array[ j++ ];
        }

        // 把新数组中的数覆盖nums数组
        for (int k2 = 0; k2 < temp.length; k2++) array[ k2 + low ] = (T) temp[ k2 ];
    }

    public static <T> void mergeSort(T[] array, Comparator<? super T> comparator) {
        mergeSort(array, 0, array.length - 1, comparator);
    }

    public static <T> void mergeSort(T[] array, int low, int high, Comparator<? super T> comparator) {
        int mid = (low + high) >> 1;
        if (low < high) {
            mergeSort(array, low, mid, comparator);
            mergeSort(array, mid + 1, high, comparator);
            mergeCompare(array, low, mid, high, comparator);
        }
    }


    private static <T> void mergeCompare(T[] array, int low, int mid, int high, Comparator<? super T> comparator) {
        Object[] temp = new Object[ high - low + 1 ];
        int i = low;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= high) {
            if (comparator.compare(array[ i ], array[ j ]) <= 0)
                temp[ k++ ] = array[ i++ ];
            else
                temp[ k++ ] = array[ j++ ];
        }
        while (i <= mid)
            temp[ k++ ] = array[ i++ ];
        while (j <= high)
            temp[ k++ ] = array[ j++ ];

        for (int index = 0; index < temp.length; index++) array[ index + low ] = (T) temp[ index ];
    }
}
